The use of multiple processors executing operations in parallel within a computer system has long been recognized as a means for increasing computational performance and throughput of the system. However, to generate correct and repeatable results in such a system, communication between the various processors must occur in a controlled manner. To facilitate this communication, the processors often access the same data memory locations within a shared memory space to transfer messages or other data therebetween, as well as to access and possibly modify other data shared between processors. In one example, each of the processors may require “atomic” read-modify-write access to one or more of these memory locations to avoid corrupting or compromising the data within these locations. In other words, each of the processors may need to perform multiple operations on a particular datum without allowing access to these same locations by another processor.
In some computer systems, hardware-intensive constructs called “locks,” such as binary semaphores, counting locks and spinlocks, have been employed to provide controlled access to data shared between processors. Generally, a processor that successfully accesses a lock or similar construct has uninterruptible access to one or more memory locations protected by the lock until the processor decides to release the lock. While locks are effective at controlling access to data shared between processors, locks essentially implement a blocking scheme, meaning that other processors requiring access to the same data are temporarily halted while another processor possesses the lock, thus negatively impacting system performance. The amount of blocking is also affected by the degree of granularity of the shared data being protected by one or more locks. For example, under high granularity, in which each lock protects a relatively small amount of data, the amount of overhead associated with the locks is increased, but the amount of contention for any single lock is reduced. Oppositely, low granularity, in which each lock protects more data, results in fewer locks being implemented, but also causes more contention for each lock. This blocking or contention is exacerbated if the processor with the lock fails. Other well-known maladies associated with locks, such as deadlock, livelock, and priority inversion, are also problematic. Further, use of the locks often significantly increases unnecessary overhead, as the odds of two or more processors accessing the same shared memory location at any one time are relatively low in most computer systems.
To address these problems, the concept of transactional memory was developed. Instead of employing a hardware blocking scheme, transactional memory utilizes a more optimistic, software-oriented approach. Generally, a processor tentatively executes a series of operations, termed a “transaction,” on one or more memory locations without regard to the actions of other processors, so no blocking occurs at that point. Concurrently, the processor records the operations in a log. After the necessary operations, the processor then “validates,” or verifies that other processors have not accessed the same shared data. If not, all changes made to the data are “committed,” or made permanent. Otherwise, a conflict may have occurred, thus requiring the processor to reverse all of the associated memory changes and abort the transaction. In that case, the processor is typically free to reattempt the transaction immediately.
While software-based transactional memory is believed to be an effective and efficient alternative to current hardware-based blocking schemes, a significant amount of software overhead is normally incurred, thus detracting from some of the benefits that transactional memory provides.